﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace TooWhite.Sort
{
    /// <summary>
    /// 排序器
    /// </summary>
    public static class Sorter
    {
        /*
            用于计算执行时间的代码：
            TimeSpan now = new TimeSpan(DateTime.Now.Ticks);
            
            ...

            TimeSpan then = new TimeSpan(DateTime.Now.Ticks);
            TimeSpan ts = then.Subtract(now).Duration();
            return ts.TotalMilliseconds;
          
        */
        public static double InsertSort<T>(this T[] array) where T : IComparable<T>
        {
            TimeSpan now = new TimeSpan(DateTime.Now.Ticks);

            for (int i = 1; i < array.Length; i++)
            {
                T guard = array[i];
                for (int j = i - 1; j >= 0; j--)
                {
                    if (guard.CompareTo(array[j]) > 0)
                    {
                        array[j + 1] = guard;
                        break;
                    }
                    else
                    {
                        array[j + 1] = array[j];
                    }

                    array[j] = guard;
                }
            }

            TimeSpan then = new TimeSpan(DateTime.Now.Ticks);
            TimeSpan ts = then.Subtract(now).Duration();
            return ts.TotalMilliseconds;
        }

        public static double BubbleSort<T>(this T[] array) where T : IComparable<T>
        {
            TimeSpan now = new TimeSpan(DateTime.Now.Ticks);

            for (int i = 0; i < array.Length - 1; i++)
            {
                bool hasswaped = false;
                for (int j = i + 1; j < array.Length; j++)
                {
                    if (array[i].CompareTo(array[j]) > 0)
                    {
                        hasswaped = true;
                        T temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                    }
                }
                if (hasswaped == false) break;
            }

            TimeSpan then = new TimeSpan(DateTime.Now.Ticks);
            TimeSpan ts = then.Subtract(now).Duration();
            return ts.TotalMilliseconds;
        }

        public static double QuickSort<T>(this T[] array) where T : IComparable<T>
        {
            TimeSpan now = new TimeSpan(DateTime.Now.Ticks);

            DoQuickSort(array, 0, array.Length - 1);

            TimeSpan then = new TimeSpan(DateTime.Now.Ticks);
            TimeSpan ts = then.Subtract(now).Duration();
            return ts.TotalMilliseconds;
        }

        public static double SelectionSort<T>(this T[] array) where T : IComparable<T>
        {
            TimeSpan now = new TimeSpan(DateTime.Now.Ticks);

            for (int i = 0; i < array.Length; i++)
            {
                int min = i;
                for (int j = i; j < array.Length; j++)
                {
                    if (array[j].CompareTo(array[min]) < 0) min = j;
                }
                T temp = array[i];
                array[i] = array[min];
                array[min] = temp;
            }

            TimeSpan then = new TimeSpan(DateTime.Now.Ticks);
            TimeSpan ts = then.Subtract(now).Duration();
            return ts.TotalMilliseconds;
        }

        public static double ShellSort<T>(this T[] array) where T : IComparable<T>
        {
            TimeSpan now = new TimeSpan(DateTime.Now.Ticks);

            int[] delta = GetDeltaArray(array.Length);
            int t = (int)Math.Log(array.Length + 1, 2);

            for (int i = 0; i < t; i++)
            {
                ShellInsert(array, delta[i]);
            }

            TimeSpan then = new TimeSpan(DateTime.Now.Ticks);
            TimeSpan ts = then.Subtract(now).Duration();
            return ts.TotalMilliseconds;
        }
        

        #region 希尔排序内部调用方法
        static int[] GetDeltaArray(int n)
        {
            int t = (int)Math.Log(n + 1, 2);
            int[] rst = new int[t];
            for (int k = 1; k <= t; k++)
            {
                rst[k - 1] = (int)Math.Pow(2, t - k + 1) - 1;
            }
            return rst;
        }

        static void ShellInsert<T>(this T[] array, int dk) where T : IComparable<T>
        {
            for (int i = dk; i < array.Length; i++)
            {
                T temp = array[i];
                if (array[i].CompareTo(array[i - dk]) < 0)
                {
                    int j = 0;
                    for (j = i - dk; j >= 0 && temp.CompareTo(array[j]) < 0; j -= dk)
                    {
                        array[j + dk] = array[j];
                    }
                    array[j + dk] = temp;
                }
            }
        }
        #endregion

        #region 快速排序内部调用方法
        static int Partition<T>(T[] array, int low, int high) where T : IComparable<T>
        {
            int i, j;
            i = low;
            j = high;

            T temp = array[low];
            int it = FindMiddle<T>(array, low, high, (int)((low + high) / 2));
            array[low] = array[it];
            array[it] = temp;

            T pivot = array[low];
            while (i < j)
            {
                while (i < j && array[j].CompareTo(pivot) >= 0) j--;
                array[i] = array[j];
                while (i < j && array[i].CompareTo(pivot) <= 0) i++;
                array[j] = array[i];
            }

            array[i] = pivot;
            return i;
        }

        static int FindMiddle<T>(T[] array, int a, int b, int c) where T : IComparable<T>
        {
            if (array[a].CompareTo(array[b]) >= 0 && array[a].CompareTo(array[c]) >= 0) return array[b].CompareTo(array[c]) >= 0 ? b : c;
            if (array[b].CompareTo(array[a]) >= 0 && array[b].CompareTo(array[c]) >= 0) return array[a].CompareTo(array[c]) >= 0 ? a : c;
            if (array[c].CompareTo(array[b]) >= 0 && array[c].CompareTo(array[a]) >= 0) return array[a].CompareTo(array[b]) >= 0 ? a : b;

            throw new Exception("未知错误");
        }

        static void DoQuickSort<T>(this T[] array, int low, int high) where T : IComparable<T>
        {
            if (low < high)
            {
                int i = Partition(array, low, high);
                DoQuickSort(array, low, i - 1);
                DoQuickSort(array, i + 1, high);
            }
        }
        #endregion
    }

    /// <summary>
    /// 测试数据生成器
    /// </summary>
    public static class TestDataGenerater
    {
        public static int[] GetRandomIntArray(int length)
        {
            int[] array = new int[length];
            Random ran = new Random();
            for (int i = 0; i < length; i++)
            {
                array[i] = ran.Next();
            }

            return array;
        }

        public static int[] GetOrdinalIntArray(int length, bool reversed = false)
        {
            int[] array = new int[length];
            for (int i = 0; i < length; i++)
            {
                array[i] = reversed ? length - i : i;
            }

            return array;
        }

        public static List<int[]> CopyIntArray(this int[] array, int amount)
        {
            List<int[]> rst = new List<int[]>();
            for (int i = 0; i < amount; i++)
            {
                rst.Add(array.Clone() as int[]);
            }

            return rst;
        }
    }

    /// <summary>
    /// 控制台输出助手
    /// </summary>
    public static class OutputHelper
    {
        public static void OutputOnConsole<T>(this T[] array)
        {
            for (int i = 0; i < array.Length; i++)
            {
                Console.Write("{0, 8}", array[i]);
            }
        }
    }
}
